package kyssion.leetcode.num51_100;

import kyssion.leetcode.util.ShowUtil;

/**
 * 给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
 *
 * 示例 1:
 *
 * 输入:
 * [
 *   [1,1,1],
 *   [1,0,1],
 *   [1,1,1]
 * ]
 * 输出:
 * [
 *   [1,0,1],
 *   [0,0,0],
 *   [1,0,1]
 * ]
 * 示例 2:
 *
 * 输入:
 * [
 *   [0,1,2,0],
 *   [3,4,5,2],
 *   [1,3,1,5]
 * ]
 * 输出:
 * [
 *   [0,0,0,0],
 *   [0,4,5,0],
 *   [0,3,1,0]
 * ]
 * 进阶:
 *
 * 一个直接的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
 * 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
 * 你能想出一个常数空间的解决方案吗？
 */
public class code73_矩阵置0 {
    public static void main(String[] args) {
        int[][] iii = new int[][]{
                {8, 3, 1, 4, 6, 4, 0, 3, 4},
                {9, 1, 3, 0, 1, 5, 7, 4, 1},
                {2, 2, 5, 2147483647, 5, 4, 4, 3, 8},
                {4, 9, 7, 0, 3, 6, 9, 5, 9},
                {4, 1, 8, 8, 4, 1, 5, 7, 6}};
        new code73_矩阵置0().setZeroes(iii);
        ShowUtil.showArrarr(iii);
    }

    /**
     * 两个boolean类型处理实现最小匹配
     * @param matrix
     */
    public void setZeroes(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        boolean lz = false;
        for (int a = 0; a < matrix[0].length; a++) {
            if (matrix[0][a] == 0) {
                lz = true;
                break;
            }
        }
        boolean pz = false;
        for (int a = 0; a < matrix.length; a++) {
            if (matrix[a][0] == 0) {
                pz = true;
                break;
            }
        }
        //lie
        for (int a = 1; a < matrix.length; a++) {
            for (int b = 0; b < matrix[a].length; b++) {
                if (matrix[a][b] == 0) {
                    matrix[a][0] = 0;
                }
            }
        }
        for (int a = 1; a < matrix[0].length; a++) {
            for (int b = 0; b < matrix.length; b++) {
                if (matrix[b][a] == 0) {
                    matrix[0][a] = 0;
                    break;
                }
            }
        }

        for (int b = 1; b < matrix[0].length; b++) {
            if (matrix[0][b] == 0) {
                for (int a = 1; a < matrix.length; a++) {
                    matrix[a][b] = 0;
                }
            }
        }

        for (int b = 1; b < matrix.length; b++) {
            if (matrix[b][0] == 0) {
                for (int a = 1; a < matrix[b].length; a++) {
                    matrix[b][a] = 0;
                }
            }
        }

        if (lz) {
            for (int a = 0; a < matrix[0].length; a++) {
                matrix[0][a] = 0;
            }
        }
        if (pz) {
            for (int a = 0; a < matrix.length; a++) {
                matrix[a][0] = 0;
            }
        }
    }
}
